/**
 * 二叉树节点定义
 */
export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

/**
 * 计算二叉树的直径
 * 二叉树的直径是指任意两个节点之间最长路径上的节点数
 * 注意：路径可能穿过也可能不穿过根节点
 * 
 * 算法思路：
 * 1. 使用深度优先搜索（DFS）遍历每个节点
 * 2. 对于每个节点，计算经过它的最长路径 = 左子树深度 + 右子树深度
 * 3. 在递归过程中更新全局最大值
 * 4. 返回当前节点的深度 = 1 + max(左子树深度, 右子树深度)
 * 
 * @param root 二叉树的根节点
 * @returns 二叉树的直径（最长路径上的节点数）
 */
function diameterOfBinaryTree(root: TreeNode | null): number {
    // 记录全局最大直径
    let res = 0
    
    /**
     * 递归计算以当前节点为根的子树的深度
     * 同时更新经过当前节点的最长路径
     * 
     * @param root 当前节点
     * @returns 以当前节点为根的子树的最大深度
     */
    function depth(root: TreeNode | null): number {
        // 空节点深度为0
        if (!root) return 0
        
        // 递归计算左子树和右子树的深度
        const left = depth(root.left)
        const right = depth(root.right)
        
        // 更新全局最大值：经过当前节点的最长路径 = 左子树深度 + 右子树深度
        res = Math.max(res, left + right)
        
        // 返回当前节点的深度 = 1（当前节点） + 左右子树中较深的那个
        return 1 + Math.max(left, right)
    }
    
    // 从根节点开始遍历
    depth(root)
    
    // 返回全局最大直径
    return res
};